پایان نامه کارشناسی ارشد رشته مهندسی نرم افزار با عنوان
بررسی طبقه بندی جریان داده ها در یک محیط پویا و کاربرد عامل و سیستمهای چندعامله در داده کاوی
*پاورپوینت همین پایان نامه با 53 اسلاید بصورت رایگان ضمیمه شده است:)-
چکیده
امروزه با توجه به گسترش روز افزون اطلاعاتی که بشر با آنها سر و کار دارد، بهره گیری از روشهایی همچون داده کاوی برای استخراج دانش و اطلاعات نهفته در داده ها، امری غیرقابل اجتناب می باشد. بدلیل حجم بسیار بالای داده ها در بسیاری از کاربردها و اهمیت بیشتر داده های جدید، ذخیره سازی این داده ها امری مقرون به صرفه نیست، لذا داده هایی که باید مورد پردازش قرار گیرند، همواره بصوت پویا در حال تغییر و تحول هستند. مساله دیگری که امروزه در بحث داده کاوی وجود دارد، بحث توزیع شدگی ذاتی داده ها است. معمولا پایگاههایی که این داده ها را ایجاد یا دریافت می کنند، متعلق به افراد حقیقی یا حقوقی هستند که هر کدام بدنبال اهداف و منافع خود می باشند و حاضر نیستند دانش خود را بطور رایگان در اختیار دیگران قرار دهند.
با توجه به قابلیتهای عامل و سیستمهای چندعامله و مناسب بودن آنها برای محیطهای پویا و توزیع شده بنظر می رسد که بتوان از قابلیتهای آنها برای داده کاوی در محیطهای پویا و محیطهای توزیع شده بهره برد. اکثر کارهایی که تاکنون در زمینه بهره-گیری از عامل و سیستمهای چندعامله انجام شده است خصوصیتهایی همانند خودآغازی و بخصوص متحرک بودن عاملها را مورد بررسی قرار داده است و در آنها مواردی همچون هوشمندی، یادگیری، قابلیت استدلال، هدفگرایی و قابلیتهای اجتماعی عاملها مورد بررسی قرار نگرفته است. در این تحقیق ما قصد داریم تا ضمن بررسی کارهای موجود در زمینه کاربرد عامل و سیستمهای چندعامله در داده کاوی، بحث طبقه بندی جریان داده ها را در یک محیط پویا مورد بررسی قرار دهیم.
ما مساله خود را در دو فاز مورد بررسی قرار خواهیم داد. در فاز اول خصوصیتهای یک عامل تنها مورد بررسی قرار خواهد گرفت و در فاز دوم قابلیتهای اجتماعی عاملها مانند مذاکره، دستیابی به توافق و ... برای داده کاوی در یک محیط پویا و توزیع شده رقابتی مورد استفاده قرار خواهد گرفت. بطور کلی دستاوردهای اصلی این تحقیق عبارتند از 1) ارائه یک رویکرد مبتنی بر عامل برای مساله طبقه بندی جریان داده های دارای تغییر مفهوم و پویا با استفاده از قابلیتهای هدفگرایی، هوشمندی، یادگیری و استدلال 2) ارائه یک رویکرد مبتنی بر سیستمهای چندعامله برای طبقه بندی جریان داده های توزیع شده در یک محیط رقابتی با استفاده از قابلیتهای اجتماعی عاملها و دستیابی به توافق. نتایج حاصل از آزمایشات انجام شده در این پایان نامه نشان دهنده برتری استفاده از عاملها و سیستمهای چندعامله برای بحث طبقه بندی و داده کاوی در محیطهای پویا و توزیع شده می باشد.
کلمات کلیدی:
داده کاوی
جریان داده
معماری BDI
عاملها و سیستمهای چندعامله
طبقه بندی جریان داده ها در یک محیط پویا
استخراج دانش و اطلاعات نهفته در داده ها
مقدمه ای بر داده کاوی
داده کاوی به معنای یافتن نیمه خودکار الگوهای پنهان موجود در مجموعه داده های موجود می باشد[38]. داده کاوی از مدلهای تحلیلی ، کلاس بندی و تخمین و برآورد اطلاعات و ارائه نتایج با استفاده از ابزارهای مربوطه بهره می گیرد. می توان گفت که داده کاوی در جهت کشف اطلاعات پنهان و روابط موجود در بین داده های فعلی و پیش بینی موارد نامعلوم و یا مشاهده نشده عمل می کند. برای انجام عملیات داده کاوی لازم است قبلا روی داده های موجود پیش پردازشهایی انجام گیرد. عمل پیش پردازش اطلاعات خود از دو بخش کاهش اطلاعات و خلاصه سازی و کلی سازی داده ها تشکیل شده است.
کاهش اطلاعات عبارت است از تولید یک مجموعه کوچکتر، از داده های اولیه، که تحت عملیات داده کاوی نتایج تقریبا یکسانی با نتایج داده کاوی روی اطلاعات اولیه به دست دهد[38]. پس از انجام عمل کاهش اطلاعات و حذف خصایص غیر مرتبط نوبت به خلاصه سازی و کلی سازی داده ها می رسد. داده-های موجود در بانک های اطلاعاتی معمولا حاوی اطلاعات در سطوح پایینی هستند، بنابراین خلاصه سازی مجموعه بزرگی از داده ها و ارائه آن به صورت یک مفهوم کلی اهمیت بسیار زیادی دارد. کلی سازی اطلاعات، فرآیندی است که تعداد زیادی از رکوردهای یک بانک اطلاعاتی را به صورت مفهومی در سطح بالاتر ارائه می نماید. خود روشهای داده کاوی به سه دسته کلی تقسیم می شوند که عبارتند از خوشه بندی، طبقه-بندی و کشف قواعد وابستگی. در ادامه هر یک از این روشها را بطور کلی معرفی می نماییم.
فهرست مطالب
1. فصل اول - معرفی و آشنایی با مفاهیم اولیه1
1-1- مقدمه ای بر داده کاوی2
1-1-1- خوشه بندی3
1-1-2- کشف قواعد وابستگی4
1-1-3- طبقه بندی4
1-1-3-1- طبقه بندی مبتنی بر قواعد5
1-2- داده کاوی توزیع شده7
1-3- عاملها و سیستمهای چندعامله8
1-3-1- عامل8
1-3-1-1- مقایسه عامل با شی9
1-3-1-2- معماری عاملها11
1-3-1-3- معماری BDI12
1-3-2- سیستم های چندعامله14
1-3-2-1- مذاکره17
1-4- بهره گیری از عامل برای داده کاوی19
1-4-1- سیستم های چندعامله، بستری برای داده کاوی توزیع شده19
1-5- جمع بندی22
2. فصل دوم - داده کاوی پویا23
2-1- مقدمه ای بر داده کاوی پویا24
2-2- جریان داده25
2-3- طبقه بندی جریان داده26
2-3-1- موضوعات پژوهشی27
2-4- جمع بندی31
3. فصل سوم - مروری بر کارهای انجام شده33
3-1- مقدمه34
3-2- داده کاوی توزیع شده ایستا35
3-2-1- روشهای غیرمتمرکز36
3-2-2- روشهای مبتنی بر توزیع ذاتی داده ها37
3-3- کارهای مهم انجام شده در زمینه داده کاوی با استفاده از عامل38
3-4- کارهای انجام شده در زمینه طبقه بندی جریان داده ها41
3-4-1- روشهای طبقه بندی Ensemble-based41
3-4-2- درختهای تصمیم بسیار سریع43
3-4-3- طبقه بندی On-Demand46
3-4-4- OLIN48
3-4-5- الگوریتمهای LWClass49
3-4-6- الگوریتم ANNCAD51
3-4-7- الگوریتم SCALLOP51
3-4-8- طبقه بندی جریان داده ها با استفاده از یک روش Rule-based53
3-5- جمع بندی54
4. فصل چهارم - تعریف مساله55
4-1- مقدمه56
4-2- تعریف مساله برای فاز اول56
4-2-1- جریان داده57
4-2-2- مفهوم یا مدل موجود در جریان داده57
4-2-3- مساله طبقه بندی جریان داده های دارای تغییر مفهوم57
4-3- تعریف مساله برای فاز دوم59
5. فصل پنجم - رویکردهای پیشنهادی62
5-1- مقدمه63
5-2- رویکرد پیشنهادی برای فاز اول پروژه63
5-2-1- عامل و ویژگیهای آن در این مساله64
5-2-2- عملکرد کلی عامل65
5-2-3- معماری عامل66
5-2-3-1- حسگرها 67
5-2-3-2- پایگاه دانش عامل68
5-2-3-3- تابع ارزیابی محیط70
5-2-3-3-1- نحوه تشخیص اطلاعات و نگهداری الگوهای recur در جریان داده70
5-2-3-3-2- نحوه استخراج الگوهای recur70
5-2-3-3-3- نحوه بروزرسانی اطلاعات مربوط به الگوهای recur73
5-2-3-3-4- نحوه محاسبه وقوع احتمال وقوع یک الگوی خاص74
5-2-3-4- تابع سودمندی75
5-2-3-5- بخش تصمیم گیری و Planning79
5-2-3-5-1- بخش تصمیم گیری79
5-2-3-5-2- Planning83
5-2-3-6- بخش Action86
5-3- رویکرد پیشنهادی برای فاز دوم مساله87
5-3-1- عاملهای مشتری88
5-3-2- عامل صفحه زرد90
5-3-3- عاملهای داده کاو91
5-3-3-1- معماری عاملهای داده کاو92
5-3-3-1-1- تابع BRF94
5-3-3-1-2- تابع Generate Options95
5-3-3-1-3- تابع فیلتر95
5-3-3-1-4- بخش Actions96
5-3-3-1-5- Plan های عامل97
5-3-3-1-5- 1- Plan مربوط به طبقه بندی97
5-3-3-1-5-2- Plan مربوط به تطبیق طبقه بند 98
5-3-3-1-5-3- Plan مربوط به خرید و فروش قواعد با استفاده از مذاکره101
5-4- جمع بندی111
6. فصل ششم - آزمایشات و نتایج113
6-1- مقدمه114
6-2- محیط عملیاتی114
6-3- مجموعه داده های مورد استفاده116
6-3-1- مجموعه داده های استاندارد116
6-3-2- مجموعه داده های واقعی117
6-4- معیارهای ارزیابی و روشهای مورد استفاده برای مقایسه117
6-5- آزمایشات انجام شده118
6-5-1- آزمایشات مربوط به فاز اول119
6-5-2- آزمایشات مربوط به فاز دوم128
6-6- جمع بندی130
7. فصل هفتم- جمع بندی و نتیجه گیری132
فهرست مراجع136
فهرست اشکال
شکل 1-1- معماری BDI در عامل15
شکل 3-1- درخت تحقیق مربوط به طبقه بندی در مبحث داده کاوی34
شکل 3-2- طبقه بندی مبتنی بر Ensemble.44
شکل 3-3- چارچوب روش On-Demand47
شکل 3-4- نمایی از سیستم OLIN49
شکل 3-5- پروسه SCALLOP53
شکل 5-1- نمودار ترتیب عملکرد عامل پیشنهادی66
شکل 5-2- معماری عامل پیشنهادی67
شکل 5-3- پنجره نظاره بر روی جریان داده ها68
شکل 5-4- گراف ایجاد شده از روی رشته مفهوم ها71
شکل 5-5- محل تجمع الگوهای استخراج شده از رشته مفهوم ها73
شکل 5-6- میزان محاسبه شده احتمالها به ازای مقادیر مختلف K81
شکل 5-7- شبه کد Plan کلی عامل83
شکل 5-8- نسبت واریانس به حاصلضرب 50 متغیر دارای مجموع ثابت85
شکل 5-9- وزن دهی چند داده مختلف86
شکل 5-10- نمایی کلی از سیستم چندعامله ایجاد شده88
شکل 5-11- معماری BDI عامل داده کاو93
شکل 5-12- بخشی از جریان داده و قواعد استخراج شده از آن99
شکل 5-13- بخشی از جریان داده و قواعد استخراج شده از آن101
شکل 6-1- کد نمونه برای استفاده از بسته نرم افزاری weka115
شکل 6-2- زمان لازم بر حسب میلی ثانیه برای داده های Stagger 120
شکل 6-3- زمان مصرف شده برای تطبیق طبقه بند120
شکل 6-4- نمودار مربوط به زمان پردازش روشهای مختلف برای داده های HyperPlan 121
شکل 6-5- زمان مصرف شده برای تطبیق طبقه بند 121
شکل 6-6- نمودار مربوط به زمان پردازش روشهای مختلف برای داده های Nursery 122
شکل 6-7- زمان مصرف شده برای تطبیق طبقه بند برای داده های Nursery 122
شکل 6-8- عملکرد روشهای مختلف بر روی مجموعه داده HyperPlan 124
شکل 6-9- نمودار عملکرد روشهای مختلف بر روی مجموعه داده HyperPlan در یک بازه کوچکتر 124
شکل 6-10- نمودار عملکرد روشهای مختلف بر روی مجموعه داده HyperPlan در یک بازه کوچکتر 125
شکل 6-11- زمان مصرف شده برای تطبیق طبقه بند برای داده های HyperPlan 125
شکل 6-12- عملکرد روشهای مختلف بر روی مجموعه داده Stagger 126
شکل 6-13- زمان مصرف شده برای تطبیق طبقه بند برای داده های Stagger 126
شکل 6-14- عملکرد روشهای مختلف بر روی مجموعه داده Nursery 127
شکل 6-15- زمان مصرف شده برای تطبیق طبقه بند برای داده های Nursery 127
شکل 6-16- نمودار نتایج حاصل از طبقه بندی توزیع شده مجموعه داده Nursery 130
فهرست جدولها
جدول 1-1- ویژگیهای یک عامل 11
جدول 3-1- ماتریس حاصل از روش LWClass51
جدول 3-2- مقایسه تکنیکهای ذکر شده54
جدول 5-1- ساختار اطلاعاتی ذخیره شده برای هر مفهوم و الگو69
جدول 5-2- ساختار اطلاعاتی مربوط به وقوع الگوی "CFDA"75
جدول 5-3- نمونه ای از خروجی تابع سودمندی عامل81
جدول 5-4- اطلاعات مورد استفاده برای تخمین سودمندی یک قاعده105
جدول 6-1- دقت طبقه بندی روشهای مختلف128
جدول 6-2- نتایج حاصل از طبقه بندی توزیع شده مجموعه داده Nursery در سه مفهوم مختلف130
دانلود طرح توجیهی پوشال کولر